#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@gosun>
#
# Distributed under terms of the MIT license.

"""
# 这里有个动画
http://www.learningandtheadolescentmind.com/resources_02_bucket.html
"""

class ObtainBucket:
    def __init__(self, capacities, states, result):

        self.result = result
        self.caps  = capacities               # 容量
        self.cur   = states                   # 当前水桶中水量
        self.queue = [self.cur]               # 队列
        self.states_set = { tuple(self.cur) } # 判断是否已经处理过, 用来剪枝(并添加第一个状态)
        self.len =  len(self.cur)

    def obtain(self):
        # 返回 drop_water_path, end state
        if self.result in self.cur:
            return [], self.cur

        level = -1
        while self.queue:
            # level += 1
            top_state =  self.queue.pop()

            # print(level, "===>", top_state)
            print(top_state)

            if self.spread_branch(top_state):
                return True

        return False

    def spread_branch(self, state):
        for new_state in self.spread_states(state):
            if tuple(new_state) in self.states_set:
                continue

            self.states_set.add(tuple(new_state))
            self.queue.insert(0, new_state)

            # 分出一个self.result来
            # if self.result in new_state:
            # 分出两个4来
            # 如果去掉这里, 会输出所有状态.
            if new_state[0] == self.result and new_state[-1] == self.result:
                print(new_state)
                return True

        return False

    def spread_states(self, state):
        for source_idx in range(self.len):

            if state[source_idx] == 0:
                continue

            for dest_idx in range(self.len):
                if source_idx == dest_idx:
                    continue

                remain = self.caps[dest_idx] - state[dest_idx]

                if remain == 0:
                    continue

                if state[source_idx] > remain:
                    drop_amount = remain
                else:
                    drop_amount = state[source_idx]

                copy_state = list(state)
                copy_state[source_idx] -= drop_amount
                copy_state[dest_idx] += drop_amount
                yield  tuple( copy_state )

def test():
    # ob = ObtainBucket([8, 3, 5], [8, 0, 0], 4)
    ob = ObtainBucket([10, 3, 7], [10, 0, 0], 5)
    ret = ob.obtain()
    print(ret)

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
